package string.leetcode.medium;

/**
 * @author bruin_du
 * @description 最长回文子串
 * @date 2022/6/5 23:40
 **/
public class Num5_LongestPalindrome {
    public String longestPalindrome(String s) {
        //方法一：动态规划
        method1(s);

        //方法二：中心扩展算法
        return method2(s);
    }

    private String method1(String s) {
        //字符串为空字符串或者长度为一直接返回
        if(s.length() < 2){
            return s;
        }
        char[] arr = s.toCharArray();
        //记录需要截取的起始下标和程度,以免频繁截取字符串影响性能
        int maxLen = 1, start = 0;
        //数组dp[i][j]保存的是arr[i,j]的回文判断结果
        boolean[][] dp = new boolean[arr.length][arr.length];
        //将对角线上为单个字符的情况初始化,因为只有一个字符肯定为回文字符串
        for (int i = 0; i < arr.length; i++) {
            dp[i][i] = true;
        }
        //只使用了数组的右上部分,因为字符串左右区间i <= j
        //对角线上就是单个字符,i == j
        //外循环为处理的字符串的长度,需要等于arr.length
        for (int L = 2; L <= arr.length; L++) {
            //里面的循环从0开始字符串
            for (int i = 0; i < arr.length; i++) {
                //i为左区间下标,j为右区间下标
                int j = L + i - 1;
                //右区间下标大于字符串的长度就跳出本层循环
                if(j >= arr.length){
                    break;
                }
                //左右两个字符不想等为直接为false
                if(arr[i] != arr[j]){
                    dp[i][j] = false;
                }else{
                    //走到这里说明左右两个字符一样
                    //当arr[i,j]的长度为2或3时,直接为true
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        //否则还需要看中间字符串的回文结果
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                //每次进行条件判断更新起始下标和长度
                if(dp[i][j] && L > maxLen){
                    start = i;
                    maxLen = L;
                }
            }
        }
        //最后根据记录的起始下标和长度截取字符串返回
        return s.substring(start,start + maxLen);
    }

    private String method2(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        int begin = 0,maxLen = 1;
        char[] arr = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            //需要考虑以偶数扩展和奇数扩展的两种情况
            int len1 = expandAroundCenter(arr,i,i);
            int len2 = expandAroundCenter(arr,i,i + 1);
            if(Math.max(len1,len2) > maxLen){
                maxLen = Math.max(len1,len2);
                begin = i - (maxLen - 1) / 2;
            }
        }
        return s.substring(begin,begin + maxLen);
    }

    private int expandAroundCenter(char[] arr,int left, int right) {
        while(left >= 0 && right < arr.length && arr[left] == arr[right]){
            left--;
            right++;
        }
        return right - left - 1 ;
    }
}
